package com.zjsru.plan2024.oneday;

import com.zjsru.common.TreeNode;

/**
 * 二叉搜索树的范围和：给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 * @Author: cookLee
 * @Date: 2024-02-26
 */
public class RangeSumBST {
    /**
     * 主
     * \
     * 输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
     * 输出：32
     * \
     * @param args args
     */
    public static void main(String[] args) {
        RangeSumBST rangeSumBST = new RangeSumBST();
        TreeNode node = new TreeNode(10,new TreeNode(5,new TreeNode(3),new TreeNode(7)),new TreeNode(15,null,new TreeNode(18)));
        int low = 7;
        int high = 15;
        System.out.println(rangeSumBST.rangeSumBST(node, low, high));
    }

    /**
     * 范围总和bst:迭代
     *
     * @param root 根
     * @param low  低
     * @param high 高
     * @return int
     */
    public int rangeSumBST(TreeNode root, int low, int high) {
        if(root == null){
            return 0;
        }
        //二叉搜索树左子树上所有节点的值均小于根节点的值，所以只考虑右子树
        if(root.val < low){
            return this.rangeSumBST(root.right , low, high);
        }
        //由于二叉搜索树右子树上所有节点的值均大于根节点的值,所以只考虑左子树
        if(root.val > high){
            return this.rangeSumBST(root.left,low, high);
        }
        //root 节点的值、左子树的范围和、右子树的范围和这三者之和
        return this.rangeSumBST(root.left,low,high) + this.rangeSumBST(root.right,low,high) + root.val;
    }
}
